
with open('data/problem067.txt') as file:
    triangle = [map(int, line.split()) for line in file.readlines()]

cache = {}
bottom = len(triangle) - 1

def search(position, depth):
    node = (position, depth)
    value = triangle[depth][position]
    if depth == bottom:
        return value
    elif node in cache:
        return cache[node]
    else:
        value1 = search(position, depth+1)
        value2 = search(position+1, depth+1) 
        result = max(value1, value2) + value
        cache[node] = result
        return result

print search(0, 0)
